1. Field of the Invention
The present invention relates to methods and apparatus for generating digital signatures.
2. Discussion of Related Art
It has become widely accepted to conduct transactions, such as financial transactions or exchange of documents, electronically. In order to verify the transaction, it is also well known to xe2x80x9csignxe2x80x9d the transaction digitally so that the authenticity of the transaction can be verified. The signature is performed according to a protocol that utilizes the message, i.e. the transaction, and a secret key associated with the party. The recipient can verify the signature using a public key of the signing party to recover the message and compare it with the transmitted message. Any attempt to tamper with the message or to use a key other than that of the signing party will result in an incompatibility between the sent message and that recovered from the signature or will fail to identify the party correctly and thereby lead to rejection of the transaction.
The signature must be performed such that the signing party""s secret key cannot be determined. To avoid the complexity of distributing secret keys, it is convenient to utilize a public key encryption scheme in the generation of the signature. Such capabilities are available where the transaction is conducted between parties having access to relatively large computing resources but it is equally important to facilitate such transactions at an individual level where more limited computing resources are available.
Automated teller machines (ATMs) and credit cards are widely used for personal transactions and as their use expands, so the need to verify such transactions increases. Transaction cards, i.e. credit/debit cards or pass cards are now available with limited computing capacity (so-called xe2x80x9cSmart Cardsxe2x80x9d) but these do not have sufficient computing capacity to implement existing digital signature protocols in a commercially viable manner.
As noted above, in order to generate a digital signature, it is necessary to utilize a public key encryption scheme. Most public key schemes are based on the Diffie Helman Public key protocol and a particularly popular implementation is that known as DSS. The DSS scheme utilizes the set of integers Zp where p is a large prime. For adequate security, p must be in the order of 512 bits although the resultant signature may be reduced mod q, where q divides pxe2x88x921, and may be in the order of 160 bits.
The DSS protocol provides a signature composed of two components r, s. The protocol requires the selection of a secret random integer k referred to as the session key from the set of integers (0,1,2, . . . qxe2x88x921), i.e.
kxcex5{0,1,2, . . . qxe2x88x921}. 
The component r is then computed such that
r={xcex2kmod p} mod q 
where xcex2 is a generator of q.
The component s is computed as
s xe2x88x92[kxe2x88x921 (h(m))+ar] mod q 
where m is the message to be transmitted,
h(m) is a hash of that message, and
a is the private key of the user.
The signature associated with the message is then s,r which may be used to verify the origin of the message from the public key of the user.
The value xcex2k is computationally difficult for the DSS implementation as the exponentiation requires multiple multiplications mod p. This is beyond the capabilities of a xe2x80x9cSmart Cardxe2x80x9d in a commercially acceptable time. Although the computation could be completed on the associated ATM, this would require the disclosure of the session key k to the ATM and therefore render the private key, a, vulnerable.
It has been proposed to precompute xcex2k and store sets of values of r and k on the card. The generation of the signature then only requires two 160 bit multiplications and signing can be completed within xc2xd second for typical applications. However, the number of sets of values stored limits the number of uses of the card before either reloading or replacement is required. A problem that exists therefore is how to generate sufficient sets of values within the storage and/or computing capacity of the card.
One possibility is to use a smaller value of p but with the DSS scheme this will jeopardize the security of the transaction.
An alternative encryption scheme that provides enhanced security at relatively small modulus is that utilizing elliptic curves in the finite field 2m. A value of m in the order of 155 provides security comparable to a 512 bit modulus for DSS and therefore offers significant benefits in implementation.
Diffie Helman Public Key encryption utilizes the properties of discrete logs so that even if a generator xcex2 and the exponentiation xcex2k is known, the value of k cannot be determined. A similar property exists with elliptic curves where the addition of two points on a curve produces a third point on the curve. Similarly, multiplying any point on the curve by an integer k produces a further point on the curve. However, knowing the starting point and the end point does not reveal the value of the integer xe2x80x98kxe2x80x99 which may then be used as a session key for encryption. The value kP, where P is an initial known point, is therefore equivalent to the exponentiation xcex2k.
In order to perform a digital signature on an elliptic curve, it is necessary to have available the session key k and a value of kP referred to as a xe2x80x9csession pairxe2x80x9d. Each signature utilizes a different session pair k and kP and although the representation of k and kP is relatively small compared with DSS implementations, the practical limits for xe2x80x9cSmart Cardsxe2x80x9d are in the order of 32 signatures. This is not sufficient for commercial purposes.
One solution for both DSS and elliptic curve implementations is to store pairs of signing elements k, kP and combine stored pairs to produce a new session pair. For an elliptic curve application, this would yield a possible 500 session pairs from an initial group of 32 stored signing elements. The possibilities would be more limited when using DSS because of the smaller group of signing elements that could be stored.
In order to compute a new session pair, k and kP, from a pair of stored signing elements, it is necessary to add the values of k, e.g. k1+k2xe2x86x92k and the values of k1P and k2P to give a new value kP. In an elliptic curve, the addition of two points to provide a third point is performed according to set formula such that the addition of a point k2P having coordinates (x,y) and a point k1P having coordinates (x2y2) provides a point k3P whose x coordinate x3 is given by:       x    3    =                                                                                          y                  1                                ⊕                                  y                  2                  2                                ⊕                                                                                      xe2x80x83                                ⁢                                                      y                    1                                    ⊕                                      y                    2                                    ⊕                                                                                                      xe2x80x83                                ⁢                                                      x                    1                                    ⊕                                                            x                      2                                        .                                                                                                                                                                                x                  1                                ⊕                                  x                  2                                                                                                      xe2x80x83                                ⁢                                                      x                    1                                    ⊕                                      x                    2                                                                                          
This computation may be significantly simplified using the normal basis representation in a field F2m, as set out more fully in our PCT Application Serial No.
PCT/CA/9500452, the contents of which are incorporated herein by reference. However, even using such advantageous techniques, it is still necessary to utilize a finite field multiplier and provide sufficient space for code to perform the computation. This is not feasible within the practical limits of available xe2x80x9cSmartxe2x80x9d cards.
As noted above, the ATM used in association with the card has sufficient computing power to perform the computation but the transfer of the coordinates of k1P and k2P from the card to the terminal would jeopardize the integrity of subsequent digital signatures as two of the stored signing elements would be known.
It is therefore an object of the present invention to obviate or mitigate the above disadvantages and facilitate the preparation of additional pairs of values from a previously stored set.
In general terms, one aspect of the present invention proposes to compute on one computing device an initial step in the computation of a coordinate of a point derived from a pair of points to inhibit recognition of the individual components, transfer such information to another computing device remote from said one device, perform at least such additional steps in said derivation at such other device to permit the completion of the derivation at said one device and transfer the result thereof to said one computing device.
Preferably, the initial step involves a simple field operation on the two sets of coordinates which provides information required in the subsequent steps of the derivation.
Preferably also the additional steps performed at the other device complete the derivation.
In a preferred embodiment, the initial step involves the addition of the x coordinates and the addition y coordinates to provide the terms (x1⊕x2) and (y1⊕y2).
The addition of the coordinates is an XOR operation that can readily be performed on the card and the results provided to the terminal.
In this manner, the coordinates (x,y) representing kP in a stored signing element are not disclosed as insufficient information is provided even with subsequent uses of the card. Accordingly, the x coordinate of up to 500 signatures can be generated from an initial set of 32 stored signing elements.
The new value of k can be computed on the card and to avoid computing the inverse kxe2x88x921, alternative known masking techniques can be utilized.
A further aspect of the present invention provides a method of generating additional sets of points from the initial set that may be used individually as a new value of kP or in combination to generate still further values of kP.
According to this aspect of the invention, the curve is an anomalous curve and the Frobenius Operator is applied to at least one of the coordinates representing a point in the initial set to provide a coordinate of a further point on the elliptic curve. The Frobenius Operator Ø provides that for a point (x1,y1) on an anomalous curve, then Ø (x1,y1) is a point (x12,y12) that also lies on the curve. In general, Øi(x1y1) is a point x2i, y2i that also lies on the curve. For a curve over the field 2m, there are m Frobenius Operators so for each value of kP stored in the initial set, m values of kP may be generated, referred to as xe2x80x9cderivedxe2x80x9d values. The new value of k associated with each point can be derived from the initial relationship between P and ØP and the initial value of k.
For a practical implementation where 32 pairs of signing elements are initially retained on the card and the curve is over the field 2155, utilizing the Frobenius Operator provides in the order of 4960 possible derived values and by combining pairs of such derived values as above in the order of 107 values of kP can be obtained from the initial 32 stored signing elements and the corresponding values of k obtained to provide 107 session pairs.
Preferably, the stored values of kP are in a normal basis representation. The application Frobenius Operator then simply requires an xe2x80x9cixe2x80x9d fold cyclic shift to obtain the value for an Øi operation.
According to a further aspect of the invention, there is provided a method of generating signature components for use in a digital signature scheme, said signature components including private information and a public key derived from said private information, said method comprising the steps of storing private information and related public key as an element in a set of such information, cycling in a deterministic but unpredictable fashion through said set to select at least one element of said set without repetition and utilizing said one element to derive a signature component in said digital signature scheme.